#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>

struct Block {
    int _id;             //分区的序号
    int _size;           //分区的大小，大小使用2^size次方表示
    int _startAddr;      //分区的开始位置
    bool _status;        //分区的状态：true为空闲，false为被占用
    int _pid;            //如果该分区被占用，则存放占用进程的id; 否则为-1
    int _actualsize;     // 实际大小

    Block(int id, int startAddr, int size, int actual)
        : _id(id)
        , _startAddr(startAddr)
        , _size(size)
        , _status(true)
        , _pid(-1)
        , _actualsize(actual)
    {}

    Block(int id, int startAddr, int size, int pid, int actual)
        : _id(id)
        , _startAddr(startAddr)
        , _size(size)
        , _status(true)
        , _pid(pid)
        , _actualsize(actual)
    {}
};

struct PCB {
    int _pid;            //进程的序号
    int _neededMem;      //需要的内存分区大小，使用2^neededMem表示
    int _status;         //1: 内存分配成功；-1：分配失败；0：还未分配
    int _blockID;        //如果分配成功，保存占用分区的id,否则为-1
    int _actualsize;     // 实际大小

    PCB(int pid, int neededMem, int actual)
        : _pid(pid)
        , _neededMem(neededMem)
        , _status(0)
        , _blockID(-1)
        , _actualsize(actual)
    {}
};

#define PROCESSNUM   10
#define TOTALMEMSIZE 1024

class BuddySystem {
private:
    // 先分配n个进程需要的内存，每个进程所需要申请内存块大小为
    // 2^k，k[3,8]
    void initPcbsSecond() {
        for (int i = 0; i < PROCESSNUM; i++) {
            int neededMem = rand() % 6 + 3;
            PCB pcb(i, neededMem, pow(2, neededMem));
            _pcbs.emplace_back(pcb);
        }
    }

    void initPcbsFirst() {
        // for (int i = 0; i < PROCESSNUM; i++) {
        //     int neededMem = rand() % 6 + 3;
        //     PCB pcb(i, neededMem, pow(2, neededMem));
        //     _pcbs.emplace_back(pcb);
        // }
        PCB onepcb(0, 7, pow(2, 7));
        PCB twopcb(1, 4, pow(2, 4));
        PCB threepcb(2, 8, pow(2, 8));
        _pcbs.insert(_pcbs.begin(), {onepcb, twopcb, threepcb});
    }

    void initBlk() {
        Block fblock(0, 0, 10, 1024);
        _free_blocks.emplace_back(fblock);
    }

    void ShowFreeBlk_UsedBlk() {
        for (auto& it : _free_blocks)
            printf("free block id: %d, size: 2^%d, startAddr: %d\n", it._id, it._size, it._startAddr);
        for (auto& it : _used_blocks)
            printf("used block id: %d, size: 2^%d, startAddr: %d, pid: %d\n", it._id, it._size, it._startAddr, it._pid);
        std::cout << "\n";
    }

    void insertFree(Block& fblock) {
        if (_free_blocks.empty()) {
            _free_blocks.emplace_back(fblock);
            return;
        }
        auto it = _free_blocks.begin();
        for (; it != _free_blocks.end(); ++it) {
            if (it->_startAddr >= fblock._startAddr)
                break;
        }
        _free_blocks.insert(it, fblock);
    }

    void insertUsed(Block& ublock) {
        if (_used_blocks.empty()) {
            _used_blocks.emplace_back(ublock);
            return;
        }
        auto it = _used_blocks.begin();
        for (; it != _free_blocks.end(); ++it) {
            if (it->_startAddr >= ublock._startAddr)
                break;
        }
        _free_blocks.insert(it, ublock);
    }

    void splitFreeBlock(std::list<Block>::iterator fit, PCB& pcb) {
        if (fit->_size == pcb._neededMem) {
            Block left(fit->_id, fit->_startAddr, fit->_size, pcb._pid, fit->_actualsize);
            _free_blocks.erase(fit);
            pcb._blockID = left._id;
            // insertUsed(left);
            _used_blocks.emplace_back(left);
            return;
        }
        Block right(_blockID + 1, fit->_startAddr + fit->_actualsize / 2, fit->_size - 1, fit->_actualsize / 2);
        _blockID++;

        int id = fit->_id;

        _free_blocks.insert(fit, right);
        // _free_blocks.emplace_back(right);
        // insertFree(right);
        // 防止出现迭代器失效
        for (auto it = _free_blocks.begin(); it != _free_blocks.end(); ++it) {
            if (it->_id == id) {
                fit = it;
                break;
            }
        }
        fit->_size -= 1;
        fit->_actualsize /= 2;
        splitFreeBlock(fit, pcb);
    }

    void MeomeryAllocation() {
        for (auto& pcb : _pcbs) {
            printf("Allocate free memory block for process #%d, of size 2^%d...\n", pcb._pid, pcb._neededMem);
            // 在freeblock中查找刚好一样的空间
            // 同时还需要记录最小能满足需求空间的空闲内存块
            auto fit = _free_blocks.begin();
            auto smallit = _free_blocks.begin();
            bool flag = false;
            for (; fit != _free_blocks.end(); ++fit) {
                if (fit->_size == pcb._neededMem)
                    break;
                if (fit->_size > pcb._neededMem && (smallit->_size < pcb._neededMem || fit->_size < smallit->_size))
                    smallit = fit;
                if (fit->_size > pcb._neededMem)
                    flag = true;
            }

            // 当前内存块也可能存在不足的情况
            if (flag == false) {
                printf("Memory allocation failed for process #%d !\n", pcb._pid);
                pcb._status = -1;
                ShowFreeBlk_UsedBlk();
                continue;
            }

            pcb._status = 1;

            if (fit != _free_blocks.end()) {
                // 说明刚好有大小一致的空闲内存块
                Block ublock(fit->_id, fit->_startAddr, fit->_size, pcb._pid, fit->_actualsize);
                pcb._blockID = ublock._id;
                _used_blocks.emplace_back(ublock);
                // insertUsed(ublock);
                _free_blocks.erase(fit);
                ShowFreeBlk_UsedBlk();
                continue;
            }

            // 走到这里说明没有大小一致的空闲内存块
            // 使用递归来拆分内存块
            splitFreeBlock(smallit, pcb);
            ShowFreeBlk_UsedBlk();
        }
    }

    using Rit = std::list<Block>::reverse_iterator;

    std::pair<Rit, bool> find_buddy(Rit& rit) {
        int buddy_start = rit->_startAddr ^ (1 << rit->_size);
        Rit cur = _free_blocks.rbegin();
        while (cur != _free_blocks.rend()) {
            if (cur->_id == rit->_id) {
                ++cur;
                continue;
            }
            if (cur->_startAddr == buddy_start && cur->_actualsize == rit->_actualsize)
                return { cur, true };
            ++cur;
        }
        return { Rit(), false };
    }

    void Combine(Rit cur) {
        std::pair<Rit, bool> buddy = find_buddy(cur);
        if (buddy.second == false) {
            return;
        }

        // 一旦合并之后，从头再一次查找合并，因为不知道是否为左兄弟还是右兄弟
        // 所以整体思路为一个递归思路

        Rit next = buddy.first;
        printf("Combine block %d an %d of size 2^%d...\n", cur->_id, next->_id, cur->_size);
        Rit first, second;
        if (cur->_startAddr < next->_startAddr) {
            first = cur;
            second = next;
        }
        else {
            first = next;
            second = cur;
        }
        first->_size += 1;
        first->_actualsize *= 2;
        // 删除被合并的元素
        for (auto it = _free_blocks.begin(); it != _free_blocks.end(); ++it) {
            if (it->_id == second->_id) {
                _free_blocks.erase(it);
                break;
            }
        }
        // 删除元素之后会存在迭代器失效的问题，需要重新找到cur元素
        for (auto it = _free_blocks.rbegin(); it != _free_blocks.rend(); ++it) {
            if (it->_id == first->_id) {
                cur = first;
                break;
            }
        }

        Combine(cur);
    }

    void MeomeryRecycle() {
        for (auto& pcb : _pcbs) {
            if (pcb._status == -1)
                continue;
            printf("Recycle used memory block for process #%d of size 2^%d\n", pcb._pid, pcb._neededMem);
            // 现在在usedblock中查找对应的内存块
            // 然后将usedblock中的内存块移动到freeblock中去
            auto uit = _used_blocks.begin();
            for (; uit != _used_blocks.end(); ++uit) {
                if (uit->_pid == pcb._pid)
                    break;
            }
            Block fblock(uit->_id, uit->_startAddr, uit->_size, uit->_actualsize);
            // 删除在used块中的空间
            _used_blocks.erase(uit);
            // 将其插入到freeblock的对应位置
            auto fit = _free_blocks.begin();
            for (; fit != _free_blocks.end(); ++fit) {
                if (fit->_startAddr < fblock._startAddr)
                    break;
            }
            _free_blocks.insert(fit, fblock);
            auto rit = _free_blocks.rbegin();
            for (; rit != _free_blocks.rend(); ++rit) {
                if (rit->_id == fblock._id)
                    break;
            }

            Combine(rit);
            ShowFreeBlk_UsedBlk();
        }
    }

public:
    BuddySystem() {
        srand(time(nullptr));
        _blockID = 0;
        
    }

    void allocationFirst() {
        initPcbsFirst();
        initBlk();
        MeomeryAllocation();
    }

    void allocationSecond() {
        initPcbsSecond();
        initBlk();
        MeomeryAllocation();
    }

    void print() {
        for (auto& pcb : _pcbs) {
            std::cout << pcb._pid << ":" << pcb._blockID << std::endl;
        }
    }

    void recycle() {
        MeomeryRecycle();
    }

private:
    std::list<PCB> _pcbs;
    std::list<Block> _free_blocks;
    std::list<Block> _used_blocks;
    size_t _blockID;
};
